package com.liuwei.spring.cloud.common.utils;
import cn.hutool.core.lang.Assert;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Maths {

    public static void main(String[] args) {
//        System.out.println(factorial(20));
//        System.out.println(factorial(2));
//        System.out.println(An(5,2));
        System.out.println(Cn(1000,125));
    }

    /**
     * permutation
     * 排列 A(n,m)=n!/(n-m)! =n×(n−1)×(n−m+1)
     * @param total
     * @param m
     * @return
     */
    public static BigInteger An(int total,int m){
        Assert.isTrue(total>0,"排列函数A(n,m)中,n需要大于0");
        Assert.isTrue(m>0,"排列函数A(n,m)中,m需要大于0");
        Assert.isTrue(m<=total,"函数C(n,m)中,m不允许大于n");
        return factorial(total).divide(factorial(total-m));
    }

    /**
     * 组合 C(n,m)= A(n,m)/m!
     * @param total
     * @param m
     * @return
     */
    public static BigInteger Cn(int total,int m){
        Assert.isTrue(total>0,"函数A(n,m)中,n需要大于0");
        Assert.isTrue(m>=0,"函数A(n,m)中,m需要大于等于0");
        Assert.isTrue(m<=total,"函数C(n,m)中,m不允许大于n");
        if (m == total || m == 0) return BigInteger.ONE;
        return factorial(total).divide(factorial(total-m)).divide(factorial(m));
    }

    /**
     * 阶乘 m!
     * 不限定 m 的最大值, BigInteger 默认不存在最大值
     */
    public static BigInteger factorial(int n) {
        // 限制递归的堆栈深度为 100, 防止递归深度异常
        for (int i = 1; i <= n ; i= i+100) {
            cache.put(String.valueOf(i),factorial(cache,i));
        }
        return factorial(cache,n);
    }

    /**
     * Map<String,BigInteger> cache
     * 缓存阶乘的值,避免重复计算
     */
    private static Map<String,BigInteger> cache = new HashMap<>();
    private static BigInteger factorial(Map<String,BigInteger> cache,int n){
        if(cache.containsKey(String.valueOf(n))){
            return cache.get(String.valueOf(n));
        }
        if (n <= 1) {
            cache.put(String.valueOf(n),BigInteger.ONE);
            return BigInteger.ONE;
        }
        BigInteger result = BigInteger.valueOf(n).multiply(factorial(cache,n-1));
        cache.put(String.valueOf(n),result);
        return result;
    }
}
